/*

给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

输入：s = "cbbd"
输出："bb"
 */

public class Test5 {

//    public String longestPalindrome(String s) {
//        int[] arr = new int[2];
//        //用于存储最大回文的大小
//        char[] chars = s.toCharArray();
//        int n = s.length();
//        for (int i = 0; i < n; i++) {
//            int high = i, low = i;
//            while (high < n - 1 && chars[i] == chars[high + 1]) {
//                high++;
//            }
//            //high小于字符串长度(最大值)和当前数值等于下一个数值时 high++
//            //排除两个相同字符串的出现
//            i = high;
//            while (low - 1 >= 0 && high + 1 < n && chars[low - 1] == chars[high + 1]) {
//                high++;
//                low--;
//            }
//            //向外扩散当两个值相等且位超过范围时扩大范围
//            if (high - low > arr[1] - arr[0]) {
//                arr[0] = low;
//                arr[1] = high;
//            }
//        }
//        return s.substring(arr[0], arr[1] + 1);
//    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("cbbd"));
        System.out.println(longestPalindrome("babad"));
    }
    public static String longestPalindrome(String s) {

        char[] str=s.toCharArray();
        int[] arr=new int[2];
        int n =s.length();
        for (int i=0;i<n;i++){
            int top=i;
            int butom=i;
            while (top<n-1 && str[i]==str[top+1]){
                top++;
            }
            i=top;
            while (top+1<n && butom-1>=0 && str[top+1]==str[butom-1]){
                top++;
                butom--;
            }

            if (top-butom>arr[0]-arr[1]){
                arr[0]=top;
                arr[1]=butom;
            }
        }

        return s.substring(arr[1] , arr[0]+1);
    }
}
